Naming

Every distributed system, and in fact every system in general, must solve the problem of naming: identifying the components it manipulates and turning the name of a component into a way to reach it. This chapter defines what naming and name resolution mean, and then presents the three families of name resolution, distinguished by the internal structure of the names involved: flat naming, structured naming, and attribute-based naming. It closes with the dual problem of detecting and removing entities that are no longer referenced.

1. Core Concepts#

1.1 Entities, Names, and Addresses#

In a distributed system, entities are the components of the system. They can be hosts, users, files, or services. Names are labels used to identify and refer to entities.

Entities are physically accessed through access points, which are themselves entities with a special kind of name called an address.

To communicate with a person, for instance, you can use different access points: email (accessed via an email address), a phone call (accessed via a phone number). The same entity can typically be accessed through multiple access points simultaneously. In some cases, different access points are valid at different times, a laptop can be connected either via Wi-Fi or via an Ethernet cable, but not both at the same time, and each interface carries a different address.

Key principle: It is not convenient to identify an entity by one of its addresses, because addresses can change (a person changes university, and their institutional email becomes invalid). It is better to use names that are valid indefinitely and location-independent.

1.2 Local vs. Global Names#

• A local name is valid only within a specific context. A filename is valid within its folder; a phone number without a country code is valid only within a country.
• A global name is valid regardless of where the naming entity is. A full file path from the root, or a phone number with a country code, is a global name.

1.3 Human-Friendly vs. Machine-Friendly Names#

• A human-friendly name is easy for people to read and remember (e.g., “my mobile”).
• A machine-friendly name is optimized for system use (e.g., a MAC address like A4:83:E7:...).

1.4 Identifiers#

Since the same logical name can map to different addresses at different times, the preferred approach is to define a unique identifier for each entity, and then maintain mappings:

Human name(s) → Unique Identifier → Address(es)

The same entity can carry multiple names (a person known as “Giovanni” at work and “papà” at home), so mapping all names to a single unique identifier is cleaner and more robust than mapping each name directly to addresses.

Resolving an ordinary name directly into an address breaks under mobility (the address changes). By utilizing identifiers, distributed systems cleanly split the tracking problem into two separate layers:

• the naming service, which maps a human- or machine-friendly name to a unique entity ID (the identifier);
• the location service, which maps that stable entity ID to the entity’s actual, changing physical address.

Names that do not depend at all on the access point used are called totally opaque names.

2. Name Resolution#

Name resolution is the process of obtaining the address of a valid access point for an entity, given one of the entity’s names.

Name resolution can be performed in three broad ways, distinguished by the structure of the names involved:

1. Flat naming: for names with no internal structure.
2. Structured naming: for names with an internal hierarchical structure.
3. Attribute-based naming: for names expressed as a list of attributes.

3. Flat Naming#

A flat name is a string with no internal structure. For example, a full name like “John Paul Google” is technically not flat, because it has components (first name + surname); a postal address is not flat either, as it consists of country, city, street, and number. Truly flat names are simple, opaque strings. Java RMI, for instance, uses flat names.

The challenge of flat naming is: given such a name, how do we implement the mapping to an address across a network?

3.1 Simple Solutions: Broadcasting and ARP#

The simplest approach is broadcasting: one node asks “Who has this name?” and the entity that owns the name replies.

The concrete example is ARP (Address Resolution Protocol), which resolves IP addresses to MAC addresses on a local area network (LAN):

• A packet arrives at the last router before its destination LAN.
• The router knows the destination IP address but not the MAC address needed to deliver the packet at the Ethernet level.
• The router broadcasts an ARP request: “Who has IP address X?”
• The machine with that IP replies with its MAC address (ARP reply).

Broadcast-based resolution is fully distributed, no single host holds all name mappings, and each host only knows its own name(s). Its drawback is that every host on the network must process every broadcast message, even just to determine it is not the target, which scales poorly. The same idea applies to multicast, where nodes subscribe to a multicast group instead of listening to the full broadcast domain.

3.2 Forwarding Pointers#

Forwarding pointers address the problem of mobile entities in a distributed object-oriented system.

Since the proxy stores the remote object’s address internally, if the object moves to a new location the stored address becomes stale.

The solution is to leave a forwarding proxy at the old location when an object moves. When a client contacts the old address:

1. The old skeleton receives the request.
2. It forwards the request through the chain to the new location.
3. The new skeleton replies to the client and includes the updated address.
4. The client’s proxy updates its stored address so future calls go directly to the new location, skipping the forwarding chain.

Analogy: before mobile phones, if you were away from home but expecting a call, you would ask a sibling to stay by the phone and forward any calls to where you actually were. When the caller reached you at the new number, you would tell them directly: “Next time, call me here.”

This mechanism is also the basis of how cellular phone calls are set up: your call initially routes to the called party’s home network (which always knows the current location), the home network connects the call to the correct antenna/cell, and the actual voice data may then flow more directly.

3.3 Home-Based Approaches#

The home-based approach generalizes the forwarding-pointer concept for persistently mobile entities. It is the scheme used by Mobile IP and cellular networks: the entity’s original (home) address effectively serves as its identifier, and the home node, assumed stable, and replicable for robustness, always knows the entity’s current location.

• Every entity has a home address: a well-known, stable point that is always reachable and always knows the entity’s current location.
• When an entity moves, it updates only the home address with its new location.
• Clients always contact the home address first; the home then forwards the connection.

This avoids continuously updating the global name resolution system (e.g., DNS) every time an entity moves.

Its drawbacks are the extra routing steps (every new connection must first reach the home address, even if the client and entity are physically close) and the resulting poor geographical scalability (if an entity permanently relocates far from its home site, every connection still incurs the cost of routing through the original home location).

Real-world analogy: if you move abroad for a year but keep your Italian phone number, calls to you from abroad are routed to Italy and then back out to your new location, even if both caller and recipient are in the same city. The monetary and network cost reflects this inefficiency, which is why people typically acquire a local number over time.

3.4 Summary of the Simple Flat-Naming Approaches#

4. Distributed Hash Tables (DHT)#

4.1 Why DHTs Are Good for Flat Name Resolution#

A hash table (also called a directory) is exactly what a name service is: a structure that maps keys to values, i.e., names to addresses. A Distributed Hash Table (DHT) extends this concept to a potentially enormous, distributed dataset, efficiently mapping keys to values even across billions of entries, without a single point of failure or a centralized bottleneck. A global phone directory with 7 billion entries is the motivating example: a DHT lets any node efficiently look up the number associated with a name, even though the directory is spread across many machines worldwide.

4.2 How a DHT Works#

The core idea is to take a large hash table, split it into chunks, and assign each chunk to a different host. Each host is responsible for a range of keys (host 1: keys 1-10; host 2: keys 11-20; and so on). These hosts are connected by virtual links (typically TCP connections) layered on top of the physical IP network, forming an overlay network.

The DHT abstraction itself is just put(id, item) / item = get(id); the overlay can be organized in many shapes, a ring (as in Chord), but also a tree, hypercube, skip list, or butterfly network, each trading routing-table size against hop count. The DHT protocol guarantees that if you query any node for a given key, that node can forward your query, in one or a small number of hops, to the node responsible for that key.

4.3 Chord: A Concrete DHT#

Chord is one of the earliest and simplest DHT designs. Its key properties:

• All nodes and keys are organized in a logical ring.
• Each node is assigned a unique m-bit identifier.
• Each key (typically a string) is hashed into an m-bit integer using a hash function.
• A key-value pair with key K is stored by the node with the smallest ID greater than or equal to K: called the successor of K.

Suppose m = 7 (128 possible positions) but only three nodes exist: 32, 90, and 105.

Positions 1-31, 33-89, etc. are simply unoccupied. In general the identifier space is chosen far larger than the number of nodes, so the ring is very sparse in node occupancy.

4.4 Lookup: The Finger Table#

In the naïve scheme, each node only knows its immediate successor, so a query hops from node to node around the ring until it reaches the responsible node. With 200 nodes this requires on average 100 hops, inefficient.

The optimized scheme gives each node a routing table (finger table) with m entries. For a node with ID n, the i-th entry points to the successor of $(n + 2^i) \bmod 2^m$. A node therefore knows not only its immediate neighbour, but also nodes that are 2, 4, 8, 16, … positions away, so the fingers fan out exponentially (roughly ½, ¼, ⅛, … of the ring). (Note that m plays a double role: it is both the number of bits of the identifiers and the number of entries in the finger table.)

To resolve key K, a node checks whether it is itself responsible for K; if not, it forwards the query to the largest node in its finger table that does not exceed K, and the receiving node repeats the process. Each hop at least halves the remaining distance to the destination, so the total number of hops is O(log N), where N is the number of nodes.

4.5 Maintaining the Finger Table#

When a new node joins the ring, it finds its own position by querying an existing node (using the same lookup procedure), then contacts its predecessor and successor to exchange routing information; existing finger tables are updated, and at most O(log N) nodes need to be touched. The same logarithmic lookup mechanism used for key searches is reused for these table updates.

4.6 Sizing the Ring#

The finger table has exactly m rows, where m is the bit-width of the key/ID space. Since everything is logarithmic, the number of hops per lookup is O(m) and each finger table holds m entries. Typical values are m = 32, m = 64, or even m = 128 for very large DHTs; with m = 128 the ring has $2^{128}$ possible positions, astronomically large, while in practice hosting only thousands or millions of nodes.

The mechanical Chord routing-table and lookup exercises seen in written exams belong to the Peer-to-Peer chapter, which develops Chord (join, stabilization, replication) in full.

5. Hierarchical Approaches for Flat Naming#

5.1 Motivation#

A single centralized server holding all name-to-address mappings is a single point of failure and a bottleneck. The hierarchical approach distributes this responsibility across a tree of name servers, each responsible for a portion of the name space (a domain).

5.2 Registration#

When an entity registers its address, the information propagates upward toward the root of the tree:

1. The entity contacts its local name server and registers: “My name is X, my address is Y.”
2. The local server records this and forwards the registration up to the next level.
3. Each intermediate node records that it can reach X via the subtree below.
4. Propagation stops when a node already has an entry for name X, or when the root is reached.

The same entity can register under multiple domains with different addresses (e.g., registered at the university domain and reachable via institutional email, and registered at the phone provider domain and reachable via phone number). Each domain independently propagates the registration upward, and the root ends up knowing that the entity has entries in multiple subtrees.

This mechanism is conceptually identical to hierarchical publish-subscribe: a subscription (registration) propagates upward, stopping at the first node that already has a matching entry.

In this hierarchy the root domain spans the entire network while leaf domains are typically a single LAN or mobile-phone cell. Location records can be created top-down or bottom-up; bottom-up creation allows the entity to be queried immediately as the record propagates. Deletion proceeds upward from the old leaf and stops at the first node that still has another child pointing to the entity (i.e., it remains reachable via a different address). A lookup that misses locally widens outward through the tree as an expanding-ring search.

5.3 Resolution (Lookup)#

To resolve a name, the client queries its local domain name server; if that server has the name it replies immediately, otherwise the query is forwarded upward through the tree until the first server that has an entry replies, and the answer propagates back down to the client.

Unlike publish-subscribe (which must reach all subscribers), name resolution stops as soon as one valid address is found. To find all addresses for an entity, the query must reach the root.

5.4 Performance Considerations#

Locality matters. Queries resolved within a local domain are very fast (the local name server responds immediately), whereas queries that must travel up to the root are slow and involve servers with increasingly large databases. The system therefore scales well when most queries are local relative to the queried entity, and poorly when many queries require reaching the upper levels of the tree.

Higher levels hold larger databases. Root-level servers must know all names in the system (though not necessarily all addresses, just which subtree to follow), and higher-level servers respond more slowly due to larger lookups.

Caching is applied at every level to reduce repeated work. Its effectiveness depends on query locality: the same names queried repeatedly in the same part of the network benefit most.

6. Structured Naming#

6.1 What Is Structured Naming?#

In a structured naming system, names have an internal structure, each component of the name carries its own meaning:

• John Paul Google, Via Blah Blah 3, Milan, Italy: a structured name composed of distinct parts: name, street, city, country.
• www.elet.polimi.it: a structured name where the dot-separated components each have meaning: it = Italy, polimi = Politecnico di Milano, elet = Department of Electronics, www = the specific machine.

By contrast, JohnPaulGoogle as a plain string is a flat name, the letters carry no individual meaning.

6.2 Name Spaces#

The canonical example of a name space is a file system.

6.3 File Systems as Name Resolution Systems#

A file system is fundamentally a name resolution mechanism: it translates a human-readable structured name (a file path) into the physical address of the file on disk (e.g., a block number on a volume).

/home/steam/mbox  →  [inode: disk block 0x3FA2...]

Each component of the path (home, steam, mbox) is a node in the graph. Directory nodes do not correspond to any data on disk, they exist only within the naming system to organize the structure. Leaf nodes hold the actual file metadata.

6.4 Hard Links vs. Symbolic Links#

File systems support two types of references.

A hard link is a direct pointer from a directory entry to the actual file entity (inode). Multiple hard links can point to the same entity from different paths:

/home/steam/keys   ─┐
                    ├─► [inode: actual file data]
/keys              ─┘

Both paths refer to exactly the same entity. If one path is removed or renamed, the other remains fully valid, hard links never break.

A symbolic link (soft link) is a special file whose content is another file name; the system must re-resolve that name to reach the actual entity:

/home/steam/mbox  →  (contains the string "/var/mail/steam/mbox")
                            ↓
                     [inode: actual file data]

Symbolic links can break: if the target name is renamed or moved, the link becomes dangling. Windows only supports symbolic links; Unix-like systems support both.

Key insight: Hard links make the name graph a directed acyclic graph (DAG). Without hard links, the name space is a pure tree.

6.5 Absolute vs. Relative Names#

• Absolute name (path): valid from the root of the name space, regardless of current location. Example: /home/steam/mbox.
• Relative name: valid only within a given current directory. Example: mbox resolves to different files depending on which directory is active.

7. Distributing a Structured Name Space#

7.1 Flat vs. Structured Distribution#

With flat names, distributing the name space means assigning complete names to different servers, each server holds a set of full name-to-address mappings.

With structured names, we can divide the name space along its structure and assign each server only a subtree. This is far more efficient: a root-level server only needs to know the first component of every name and which server handles each subtree, while lower-level servers handle more specific, deeper portions of the name space.

7.2 Three Layers of a Distributed Name Space#

A distributed structured name space is divided into three layers based on how frequently that part of the name changes. The layering concerns the distribution of resolution, not the name space itself: an ordinary file system, resolved entirely by a single machine, is a centralized naming system and needs no such division. It does, however, exhibit precisely the stability gradient that the layers formalize, the root of a disk is laid out once and essentially never changes, while files and directories at the leaves are created and removed continuously. As soon as a name space grows too large for a single machine to resolve, the tree must be split across servers, and it is split along this gradient: the stable top becomes the global layer, the volatile bottom remains local.

Why stability matters: the root servers must be queried first for every resolution, so if their content changed constantly, maintaining consistency would be prohibitively expensive. Stable upper layers allow aggressive caching, which is the key to scalability.

The three layers differ systematically along several dimensions:

8. DNS: The Domain Name System#

8.1 Structure of DNS Names#

The Domain Name System (DNS) is the most successful example of a distributed structured naming system. It maps human-readable host names to IP addresses across the entire internet. DNS names are structured right-to-left by significance:

www . elet . polimi . it
 │      │       │      └── country (Italy)
 │      │       └───────── organization (Politecnico di Milano)
 │      └───────────────── sub-domain (Dept. of Electronics)
 └──────────────────────── machine name

At the top are the Top-Level Domains (TLDs): .com, .edu, .org, .it, .uk, etc. These were defined at the creation of DNS and have been stable for decades. Below the TLDs are second-level domains administered by individual organizations (sun.com, yale.edu); at the leaves are individual machine names.

8.2 DNS Server Hierarchy#

The server tree mirrors the name-space tree:

• A small number of root servers hold the global layer: they know which servers are authoritative for each TLD.
• TLD servers (hundreds of servers) know which servers are authoritative for each second-level domain.
• Authoritative servers (thousands) hold the actual name-to-address mappings for machines within their zone.

9. DNS Resolution and Caching#

9.1 Iterative Name Resolution#

To make the distinction concrete, consider resolving ftp.cs.vu.nl, the FTP server of the Computer Science department of the Vrije Universiteit in the Netherlands.

In iterative resolution, the client’s resolver drives the entire process:

1. Client contacts the root name server → root replies: “I don’t know ftp.cs.vu.nl, but here is the address of the .nl name server.”
2. Client contacts the .nl name server → replies: “Here is the address of the name server for vu.nl.”
3. Client contacts the vu.nl name server → replies: “Here is the address of the name server for cs.vu.nl.”
4. Client contacts the cs.vu.nl name server → replies: “The IP address of ftp.cs.vu.nl is X.X.X.X.”

Each server only responds to its part of the query and hands off further responsibility to the client.

9.2 Recursive Name Resolution#

In recursive resolution, the server receiving the initial query drives the entire process:

1. Client sends the full query to the root name server.
2. Root forwards the request to the .nl name server.
3. .nl forwards to vu.nl, which forwards to cs.vu.nl.
4. cs.vu.nl resolves the name and the reply travels back up the chain to the root, which returns it to the client.

The client sends one query and receives one reply; all intermediate work happens inside the DNS infrastructure.

9.3 Trade-offs#

In practice, DNS supports both modes. Root and TLD servers prefer iterative resolution, they are too heavily loaded to hold open recursive queries for millions of clients. Lower-level servers more often use recursive resolution, taking advantage of intermediate caching. A client may request a mode, but servers are not obliged to comply.

9.4 Caching in DNS#

When a name is resolved, the result can be cached at any point in the resolution chain. Each cached record has a TTL (Time to Live); after expiry, the entry must be re-resolved.

At the global layer, TLD name-server addresses change extremely rarely, so a resolver that has cached the address of the .nl name server can safely reuse it for days. When a TLD server address does change, the transition is managed gracefully: old and new servers run in parallel until all caches have expired.

Replication is trivial precisely because global-layer data rarely changes: read-mostly data can be freely replicated without synchronization concerns, which is why root name servers are massively replicated worldwide. Operationally, each zone has a primary server and several secondary servers that periodically pull updates from the primary (about twice a day); combined with TTL-bounded caches, this permits brief, bounded inconsistencies (days at the global level) in exchange for massive scalability.

At the managerial layer, machines are added, renamed, and removed regularly, so TTLs are short and caching at higher layers is risky: a cached entry for lab2.cs.vu.nl could become stale within days.

It is theoretically possible for a root server to cache the fully resolved IP address of a specific machine and reply instantly to future queries, but in practice this never happens: individual machine names are not queried frequently enough to justify caching at the root, and their short TTLs make such entries short-lived anyway. Intermediate caching is most effective at the organizational level, where a university server caches records for its own departments.

9.5 The Administrational / Managerial Boundary#

The boundary between the administrational and managerial layers is somewhat fuzzy and context-dependent. A useful rule of thumb: the managerial layer is where machines are actually added and removed, the leaf-most zone where changes are frequent (e.g., a university department), while the administrational layer is the enclosing organizational unit (a university adding a new department is rare; a department adding a new machine is routine). Large organizations may have multiple administrational sub-layers before reaching the managerial level. The key functional criterion is always: how often does this part of the name space change?

10. DNS Record Types#

The database held by each DNS server is composed of resource records. Each record has a name, a type, and a value. The set of types was defined when the DNS standard was created and has been extended over time. (DNS names are case-insensitive, at most 255 characters in total and 63 characters per label.) Each name server is authoritative for a zone, and the tree uses no hard links.

The design principles described so far, distributed resolution, layered stability, caching, apply to any structured naming system. DNS adds a concrete record schema on top of these principles. The following examples are drawn from the zone of the Computer Science department at Vrije Universiteit in the Netherlands (cs.vu.nl).

10.1 Common Record Types#

10.2 Name Servers (NS Records)#

cs.vu.nl  NS  star.cs.vu.nl
cs.vu.nl  NS  top.cs.vu.nl
cs.vu.nl  NS  solo.cs.vu.nl

The zone cs.vu.nl is served by three name servers. Importantly, these NS records contain symbolic names, not IP addresses, they are analogous to symbolic links in a file system. To find the actual address of star.cs.vu.nl, a resolver must do a follow-up A-record query.

10.3 Mail Exchange (MX Records)#

When you send an email to [email protected], your mail client does not look up an A record for polimi.it, there may be no machine with exactly that hostname. Instead, it queries for the MX record of polimi.it to find the mail server responsible for receiving email for that domain.

cs.vu.nl  MX  1  zephyr.cs.vu.nl
cs.vu.nl  MX  2  tornado.cs.vu.nl
cs.vu.nl  MX  3  star.cs.vu.nl

The numeric priority field indicates preference, lower numbers are tried first. If zephyr is unavailable, tornado is tried, and so on.

10.4 Canonical Names (CNAME Records)#

A CNAME record defines an alias. Querying for www.cs.vu.nl might return:

www.cs.vu.nl  CNAME  top.cs.vu.nl
top.cs.vu.nl  A      130.37.20.20

There is no direct A record for www.cs.vu.nl; instead, the resolver is told to re-resolve top.cs.vu.nl. This allows multiple names to point to the same machine, and makes it easy to change the underlying machine without updating every alias.

10.5 Multiple Addresses and Reverse Lookup#

A single hostname can have multiple A records, indicating multiple network interfaces (multi-homed hosts):

star.cs.vu.nl  A  130.37.56.201
star.cs.vu.nl  A  192.31.231.42

Conversely, PTR records enable reverse resolution, mapping an IP address back to a hostname, which is used for logging, spam filtering, and diagnostics.

11. Root Name Servers#

There are exactly 13 root name servers in the DNS hierarchy, identified by the letters A through M (e.g., a.root-servers.net, j.root-servers.net). Despite there being only 13 logical root servers, each is implemented as a cluster of many physical machines distributed worldwide. As of 2023, the 13 logical servers are realized by 1,751 physical instances, operated by 12 independent organizations (see root-servers.org).

11.1 Anycast Routing#

Each of the 13 root servers has a single, globally advertised IP address. Multiple physical machines share that same IP address, and the IP routing layer uses anycast to deliver each incoming packet to whichever physical replica is topographically closest to the sender.

A query to j.root-servers.net from Europe may be answered by a machine in Frankfurt, while the same query from Asia may be answered by a machine in Tokyo; both machines share the same IP address, and the network handles the routing transparently.

11.2 Why Root Servers Can Handle the Load#

The database held by each root server is extremely small, a few hundred records, one for each TLD plus a handful of others, and fits entirely in CPU cache, enabling very fast responses. Despite this, root servers receive enormous query volumes (the J root server alone handles tens of billions of queries per day). This is manageable because the dataset is tiny and fits in memory, it is nearly read-only (no write contention), anycast distributes the load across many physical machines, and client-side and resolver-side caching means most queries never reach the root at all.

12. DNS and Mobility#

DNS was designed in the 1970s for a stable network of a few thousand hosts, and mobility is where that design shows its limits. Mobility here concerns the named entities, the hosts at the leaves of the tree, not the name servers, which are the stable backbone of the system: an entity is mobile when its network location, and with it its IP address, changes over time, whether occasionally (a server relocated to another organization) or continuously (a laptop hopping between networks). The difficulty is structural. A DNS name is not a pure identifier: delegation anchors every name to a zone, and that zone’s servers must keep answering for the name wherever the machine physically is. A move within the domain is a cheap, local update at the managerial layer; moves that cross domain boundaries, or happen frequently, undermine the assumptions the hierarchy is built on.

For a mobile node, the problem is concrete: each time it moves from one network to another its IP address changes, and for its DNS name to remain valid it would need to be re-registered with the new address, potentially on a different name server in a different zone, at every move.

This breaks the assumptions that make DNS work. The node’s name might be registered in one national/organizational zone (e.g., laptop.cs.polimi.it), but if the node is physically in Japan, the resolution must still route through Italy, incurring the overhead of home-based addressing. Keeping the name stable while the IP changes forces frequent updates on the holding zone, conflicting with the stability that makes DNS caching effective, and each update invalidates cached entries everywhere.

In practice, mobile nodes are simply not registered in DNS. When a machine moves permanently (e.g., a laptop taken abroad for a year), it is unregistered from its original zone and re-registered in the new location under a different name; anyone who previously used the old name must be informed manually, and the original name becomes a dangling reference.

Two cleaner options exist when a host keeps its name but moves to a different domain (e.g., ftp.elet.polimi.it relocating to a machine in cs.wustl.edu), both implemented by the original domain’s DNS servers:

• Return the IP address of the new location: lookups are unaffected, but further updates are no longer localized (the home zone must now track a remote machine, so the managerial layer loses its efficiency).
• Return the name of the new location: essentially a symbolic link, like a forwarding pointer. Further updates stay local, but every lookup now needs two distributed resolutions, so it is slower.

Moving within the original domain stays trivial, only that domain’s servers are updated. The difficulty is acute only for truly mobile entities.

13. Hands-On: Exploring DNS with dig#

Everything described in the previous sections can be observed on a live system. dig, the standard DNS diagnostic tool, sends a single query and prints the raw response, header flags and record sections included; it ships with macOS and Linux (on Windows it is available through WSL, with nslookup as a rough fallback). Each of the following experiments targets one mechanism from this chapter. Outputs will differ across networks and resolvers, some of which intercept DNS traffic or refuse particular queries; this variability is itself worth observing, as it reveals how many parties sit between a client and the name space.

dig +trace www.polimi.it

dig @a.root-servers.net www.polimi.it

;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 6, ADDITIONAL: 13
;; WARNING: recursion requested but not available

dig www.polimi.it

www.polimi.it.    4268    IN    A    131.175.187.72
     name          TTL   class  type      value

dig it. NS

dig polimi.it MX
dig polimi.it NS
dig polimi.it TXT
dig -x <IP-address>     # reverse lookup: use an address from a previous answer

dig @ns.polimi.it polimi.it NS

dig www.github.com

dig . NS
dig @k.root-servers.net hostname.bind CHAOS TXT +short

14. Flat vs. Structured Naming: A Comparison#

Both flat and structured naming can use a tree of name servers (as in the hierarchical approach) for distributed resolution. The fundamental difference is in how names are mapped onto that tree.

14.1 How the Mapping Differs#

Flat naming: each server holds a set of complete name-to-address pairs. If the name JohnPaul is registered in a zone, the full string is stored at that node and propagated upward, and the root must eventually know every name in the system.

Structured naming: the name space is divided along its structure. A server at each level only stores the component of the name it is responsible for; the root only needs to know the topmost component (e.g., country or TLD), not full names, and each intermediate server holds a small, stable portion of the hierarchy.

14.2 Performance Comparison#

14.3 When Flat Naming Wins#

Structured naming is generally more scalable, but flat naming can outperform it under specific conditions:

• Strong locality: if nearly all resolutions happen within the same local domain, a flat naming server can reply immediately from its local database without involving upper layers.
• When structure cannot be defined: some applications cannot organize their names into a hierarchy, for example, when names are identifiers with no inherent geographical or organizational meaning. In such cases, flat naming is the only option.

Example, ARP. ARP resolves IP addresses (which are structured) to MAC addresses. However, because ARP is by definition a local-network protocol, the resolution always happens within the same LAN. It is not worth building a distributed name-server hierarchy for something that will never leave the local segment: broadcasting achieves the same result with zero infrastructure overhead.

14.4 The Right Answer#

Neither approach is universally superior. The correct choice depends on the structure of the names (can they be organized hierarchically?), the locality of queries (are resolutions typically between nearby entities?), and the scale of the system. For internet-scale systems with globally distributed queries and billions of names, structured naming with a stable upper hierarchy, as implemented by DNS, is the clear winner. For small, local, or inherently flat name spaces, simpler flat approaches (including broadcast) are often sufficient and more practical.

15. Attribute-Based Naming#

15.1 The Concept#

Flat naming uses an opaque string with no internal structure; structured naming adds a hierarchy of components, each carrying meaning. Attribute-based naming goes one step further: each entity is described not by a single name but by a record of multiple attributes, similar to a row in a database table.

This enables a new kind of operation, searching, in addition to the traditional lookup:

• Lookup: you specify a name (or the exact key attributes) and receive back a single entity and its address. This is what DNS and flat naming systems do.
• Search: you specify a subset of attributes and receive back all matching entities, potentially many results.

15.2 LDAP: Lightweight Directory Access Protocol#

The most widely used attribute-based naming system is LDAP (Lightweight Directory Access Protocol), derived from the OSI X.500 directory service. Each entity in LDAP is described by a record of <attribute, value> pairs; each attribute has a type, and attributes may be single-valued or multi-valued (some are defined by the standard). A typical record might look like:

You can query by specifying any combination of attributes, returning a single result if you specify enough to uniquely identify the entity, or multiple results if you specify a broader subset (e.g., “all entities in the Netherlands in Amsterdam”). The full collection of such records is called the Directory Information Base (DIB).

15.3 From DIB to Directory Information Tree#

If a subset of attributes uniquely identifies every entity, for example, Country + Organization + Organizational Unit + Common Name, then that subset defines a key, the record’s Relative Distinguished Name (RDN), conventionally written like a path: /C=NL/O=Vrije Universiteit/OU=Comp. Sc./CN=Main server. This key imposes a natural hierarchy on the records, and the DIB can be reorganized as a Directory Information Tree (DIT): a structured name space where each level corresponds to one key attribute.

This tree is structurally identical to a DNS name space, and can be distributed across multiple servers using the same strategies: stable attributes at the top, less stable attributes lower down. LDAP places the most stable attributes (country, organization) at the root and the least stable (individual host names) at the leaves, for the same reason DNS does.

With the DIT in place, the system supports two modes:

• DIT-based lookup: specify all the key attributes → navigated through the tree of distributed servers → single result, returned quickly (milliseconds).
• DIB-based search: specify any subset of attributes → evaluated against a database → potentially many results, returned more slowly (seconds).

15.4 Practical Usage#

In practice, most LDAP deployments serve relatively small organizations and use only the database (DIB) approach, even for lookups, because the scale does not justify distributing the name space across multiple servers.

At scale the DIB is partitioned according to the DIT (as in DNS): each server is a Directory Service Agent (DSA) and each client a Directory User Agent (DUA), and a single query may need to consult several DSAs. What LDAP adds over a plain hierarchical naming scheme is search, e.g. search("&(C=NL)(O=Vrije Universiteit)(OU=*)(CN=Main server)").

Examples of LDAP in practice:

• Microsoft Active Directory: the user and group directory for Windows enterprise environments is built on LDAP. When you log in to a university or company network, your credentials are validated against an LDAP store.
• University login systems: at Politecnico di Milano, student and staff records (username, registration date, role, etc.) are stored in an LDAP directory. A query can retrieve a single student by exact identifier, or retrieve all students registered on a particular date.
• UDDI (Universal Description, Discovery and Integration): used in web-service (SOA) systems to publish and discover services. Each service is described by a set of attributes; clients query the registry by specifying attribute subsets to find services matching their needs.

15.5 LDAP vs. DNS#

16. Removing Unreferenced Entities#

16.1 The Problem#

A naming system stores associations between names and addresses. Over time, some of those associations become stale: an entity changes its address (e.g., a phone number is reassigned) but the old mapping remains in the directory, or an entity is deleted while references to it persist elsewhere. In both cases the system holds a reference to something no longer reachable or meaningful. These are called unreferenced entities, entries that can no longer be reached via any valid path from an active part of the system.

This problem is particularly important in distributed object-oriented systems, where objects hold references to other objects, which hold references to yet others. If a chain of references is broken at any point, every object reachable only through that chain becomes unreferenced, and should ideally be detected and cleaned up.

16.2 Garbage Collection in Centralized Systems#

In a centralized object-oriented system (such as the JVM), this problem is solved by garbage collection:

1. Define a root set: the set of objects directly referenced by active execution contexts (e.g., local variables on the call stack).
2. Starting from the root set, traverse all reachable objects (breadth-first or depth-first), marking each one as reachable.
3. Any object not marked after the traversal is unreachable: it can be garbage collected.

Key insight: an object having an incoming reference is not sufficient to prove it is reachable. Consider a cycle of objects that reference each other but are not connected to the root set, every object in the cycle has an incoming reference, yet none can be reached from any live variable. A correct garbage collector detects this and collects the entire cycle.

In a centralized system this is manageable because all threads can be paused at a consistent point, the heap traversed, and execution resumed. The entire process is synchronized on a single clock.

16.3 The Challenge in Distributed Systems#

In a distributed system there is no single global clock and no way to pause all nodes simultaneously. Objects are spread across multiple machines, references cross network boundaries, and the system continues executing during any collection attempt. Several approaches address this, each with different trade-offs.

17. Distributed Garbage Collection Techniques#

17.1 Reference Counting#

The simplest approach: each object’s skeleton maintains a counter of how many proxies to the object currently exist in the system. When a proxy is created the counter is incremented; when one is destroyed it is decremented; when it reaches zero, no client can reach the object any longer, and it can be collected.

The mechanism sounds trivial, but keeping the count correct over a network is not. Consider a process P1 holding a proxy to a remote object O, each on its own machine, so the skeleton’s counter reads 1, and suppose P1 passes its reference to a third process P2, discarding its own copy:

1. P1 sends the reference to P2 and destroys its own proxy, sending a “−1” message to O’s skeleton.
2. P2 receives the reference, creates its proxy, and sends a “+1” message to O’s skeleton.
3. The two messages travel independently, and nothing constrains their order: if the −1 arrives first, the counter momentarily reads zero, the skeleton concludes that no references exist, and O is collected. When P2’s +1 arrives, the object it refers to no longer exists, and P2 is left with a dangling reference.

Fixing the race costs messages. The race disappears if the transfer is made explicit: before sending anything to P2, P1 informs the skeleton of its intention to pass the reference; the skeleton records the incoming proxy (so the counter never dips) and acknowledges; only then does P1 transfer the reference. The count is now always correct, but a transfer that used to take one message now takes three, a real cost at scale if references are passed around frequently, and the protocol’s correctness now rests entirely on those messages being delivered reliably, which is the second problem.

Exactly-once delivery is required. Each message carries only a +1 or −1 increment, so if a message is lost or delivered twice, the counter drifts. Reference counting therefore requires exactly-once delivery, the hardest delivery guarantee to implement:

• At-most-once: easy, send and forget.
• At-least-once: send and re-send until an acknowledgement arrives; the receiver may get duplicates.
• Exactly-once: the receiver must detect and discard duplicate messages, requiring it to track message history, coordination overhead comparable to the distributed agreement problem.

Cyclic references escape the count. A group of objects forming a reference cycle each has an incoming reference from another object in the cycle, but none are reachable from any live root. Every counter reads at least 1, yet all objects are garbage; no counting protocol can detect this. It is the one limitation that cannot be repaired, and the reason distributed mark-and-sweep exists.

17.2 Weighted Reference Counting#

An improvement that eliminates the race-condition problem without adding messages. Each skeleton maintains two values: a total weight, fixed when the object is created, and a partial weight, initially equal to the total (128 in the figures below).

The weight then travels with the references, according to three rules:

• Creating a proxy from the skeleton: the proxy receives a portion, half, of the skeleton’s current partial weight (figure b).
• Passing a reference: when P1 shares its reference with P2, it passes along part of its own weight, P2 receiving half of the weight of P1’s proxy; the skeleton is not involved at all (figure c).
• Removing a proxy: the proxy gives its weight back to the skeleton, which adds it to the partial weight.

When the partial weight climbs back up to the total weight, no weight is left in the wild: no reference to the object exists any longer, and it can be collected.

This is precisely what eliminates the race condition of plain reference counting: sharing a reference sends no message to the skeleton, so the only message left in the protocol is the eventual weight return, and a race needs at least two concurrent messages to exist.

Remaining problems: cyclic references are still unsolvable; exactly-once delivery is still required for the weight-return message (a lost or duplicated decrement corrupts the partial weight); and the weight is finite, each proxy’s weight must be at least 1, so a proxy of weight 1 cannot split itself further. The workaround inserts an intermediate “stub” skeleton, which adds an indirection hop to every subsequent invocation.

17.3 Reference Listing#

Instead of a counter, the skeleton maintains a list of proxy identifiers, the addresses of all currently live proxies. When a proxy is created or copied it registers itself with the skeleton by sending its unique identifier; when destroyed, its identifier is removed; when the list is empty, the object can be collected.

Reference listing has two advantages over reference counting:

1. At-least-once delivery is sufficient. Because the list is a set (no duplicates), receiving the same registration message twice simply results in the identifier being inserted once. Duplicate messages are harmless, so there is no need to track message history: standard re-send-until-ack is enough.

2. Race conditions can be eliminated. Rather than sending an explicit remove message when a proxy is destroyed, the skeleton can periodically ping each proxy on its list; if a proxy does not respond, it is considered dead and removed. This leaves only one kind of message (registration), eliminating the two-message race.

Its costs: memory (the skeleton stores a full list of network addresses instead of a single number); delayed collection (if destruction is detected by pinging rather than explicit removal, the list may stay larger than necessary for a while); and cyclic references are still unsolvable.

In Java RMI, reference listing is the actual mechanism: a client creates its local proxy only after the server acknowledges its insertion request, and liveness is maintained through leases, the client must periodically refresh the reference, the lease interval is fixed by the runtime and non-negotiable, and UDP is used as the transport for garbage-collection traffic. A long network failure can therefore prematurely expire a lease.

17.4 Distributed Mark-and-Sweep#

The only approach that can handle cyclic references is a distributed version of the mark-and-sweep algorithm used by centralized garbage collectors.

In the centralized version, starting from the root set the collector marks reachable objects in three phases, white (not yet visited, initially all objects), grey (reachable, but outgoing references not yet followed), and black (reachable, and all outgoing references already followed), propagating grey marks along all reference edges until no grey objects remain. White objects are unreachable and can be collected.

The distributed version, pioneered by the Emerald distributed object system (Jul et al., 1988), generalizes this straightforwardly. A garbage collector runs at each site over proxies, skeletons, and objects (all initially white). When a proxy is marked grey, a message is sent to its associated skeleton, which marks its object grey and, recursively, all proxies the object contains; an acknowledgement is required before the proxy turns black. The local sweep can start as soon as every local object is black or white. Following a reference between objects on different machines thus requires a message and a reply, which makes the algorithm correct in principle but extremely expensive in practice:

• The entire distributed system must be paused for the duration of the collection. Any new proxy creation or destruction during the sweep would invalidate the in-progress marking.
• Pausing the system requires sending stop messages to every node, waiting for acknowledgements from all of them, running the sweep, then sending restart messages: potentially hundreds of messages just for coordination.
• The sweep itself generates additional messages for every reference edge that crosses a machine boundary.
• In a centralized JVM, a full GC pause lasts a few milliseconds; in a distributed system it could last seconds or longer: generally unacceptable.

In practice, distributed mark-and-sweep is rarely deployed due to the stop-the-world requirement. Java RMI uses reference listing for remote objects, supplemented by periodic liveness pinging, and standard centralized mark-and-sweep for local (intra-JVM) collection. If a local object’s remote reference list becomes empty and it is also unreachable locally, it is collected.

17.5 Summary#

No single technique is universally best. Real systems typically combine approaches: reference listing (or weighted counting) for the common case of non-cyclic references, with periodic local GC sweeps to handle any remaining intra-node cycles.

18. Exam Questions#

Questions from past written exams that map onto this chapter. The instructor does not publish official solutions: the worked answers below are unofficial, reconstructed from the course material. Naming has appeared regularly and the three themes below recur across years, so the older variants are listed together with the most recent instances.

18.1 Structured Naming over a Hierarchy of Servers#

18.2 Attribute-Based Naming and Its Scalability#

18.3 Removing Unreferenced Entities#

19. Glossary#

Compiled from G. Cugola's lectures (A.Y. 2025/26), slides + class transcriptions. Not official course material.